\bigskip
{\magonebf 5.1 Directed graphs (graph)}

{\bf 1. Definition}

An instance $G$ of the data type $graph$ consists of a list of nodes $V$ and a 
list of edges E ($node$ and $edge$ are predefined data types). Every edge $e\in 
E$ is a pair of nodes $(v,w) \in V\times V$, $v$ is called the source of $e$ and
$w$ is called the target of $e$. With every node $v$ the list of its adjacent 
edges $adj\_list(v) = \{\ e \in E\ | source(e) = v\ \}$, called the adjacency 
list of $v$, is associated.

\def\name{$graph$}
\def\type{graph}

\bigskip
{\bf 2. Creation}

\create G {}

creates an instance $G$ of type $graph$ and initializes it to the
empty graph.


\bigskip
{\bf 3. Operations}

{\bf a) Access operations}
\+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
\+\op int        indeg {node\ v}                     
                                      {returns the indegree of node $v$}
\smallskip
\+\op int        outdeg {node\ v}                     
                                      {returns the outdegree of node $v$}
\smallskip
\+\op node       source {edge\ e}               
                                      {returns the source node of edge $e$}
\smallskip
\+\op node       target {edge\ e}               
                                      {returns the target node of edge $e$}
\smallskip
\+\op int        number\_of\_nodes { }
                             {returns the number of nodes in $G$ }
\smallskip
\+\op int        number\_of\_edges { }
                             {returns the number of edges in $G$ }
\smallskip
\+\op list\<node\> all\_nodes { }
                             {returns the list $V$ of all nodes of $G$}
\smallskip
\+\op node         first\_node { }
                             {returns the first node in $V$}
\smallskip
\+\op node         last\_node { }
                             {returns the last node in $V$}
\smallskip
\+\op node         succ\_node {node\ v}
                            {returns the successor of node $v$ in $V$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op node         pred\_node {node\ v}
                            {returns the predecessor of node $v$ in $V$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op list\<edge\> all\_edges { }
                             {returns the list $E$ of all edges of $G$}
\smallskip
\+\op edge         first\_edge { }
                             {returns the first edge in $E$}
\smallskip
\+\op edge         last\_edge { }
                             {returns the last edge in $E$}
\smallskip
\+\op edge         succ\_edge {edge\ e}
                            {returns the successor of edge $e$ in $E$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op edge         pred\_edge {edge\ e}
                            {returns the predecessor of edge $e$ in $E$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op list\<edge\> adj\_edges {node\ v}  
                             {returns the list of all edges adjacent to $v$}
\smallskip
\+\op list\<node\> adj\_nodes {node\ v}  
                             {returns the list of all nodes adjacent to $v$}
\smallskip
\+\op edge   first\_adj\_edge {node\ v}
                           {returns the first edge in the adjacency list of $v$}
\smallskip 
\+\op edge   last\_adj\_edge {node\ v} 
                           {returns the last edge in the adjacency list of $v$}
\smallskip
\+\op edge   adj\_succ {edge\ e}           
                            {returns the successor of edge $e$ in the }
\+\nop                      {adjacency list of $source(e)$ }
\+\nop                      {(nil if it does not exist)}
\smallskip
\+\op edge   adj\_pred {edge\ e}          
                             {returns the predecessor of edge $e$ in the }
\+\nop                       {adjacency list of $source(e)$}
\+\nop                       {(nil if it does not exist)}
\smallskip
\+\op edge   cyclic\_adj\_succ {edge\ e}    
                             {returns the cyclic successor of edge $e$ in the}
\+\nop                       {adjacency list of $source(e)$}
\smallskip
\+\op edge   cyclic\_adj\_pred {edge\ e}    
                             {returns the cyclic predecessor of edge $e$ in the}
\+\nop                       {adjacency list of $source(e)$}
\smallskip
\+\op node   choose\_node   {}
                              {returns a node of $G$ (nil if $G$ is empty)}
\smallskip
\+\op edge   choose\_edge   {}
                              {returns an edge of $G$ (nil if $G$ is empty)}

\bigskip
{\bf b) Update operations}
\medskip
\+\op node   new\_node {}   
                             {adds a new node to $G$ and returns it}
\smallskip
\+\op void   del\_node {node\ v}      
                             {deletes $v$ and all edges adjacent to $v$}
\+\nop                       {from $G$. \precond{$indeg(v) = 0$}.}
\smallskip
\+\op edge   new\_edge {node\ v,\ w}
                             {adds a new edge $(v,w)$ to $G$ by appending }
\+\nop                       {it to the adjacency list of $v$ and returns it.}
\smallskip
\+\op edge   new\_edge {edge\ e,\ node\  w,\ rel\_pos\ dir=after} {}
\+\nop                      {adds a new edge $e\' = (source(e),w)$ to $G$ by }
\+\nop                      {inserting it after ($dir$=after) or before ($dir$}
\+\nop                      {=before) edge $e$ into the adjacency list of }
\+\nop                      {$source(e)$, returns $e\'$.}
\smallskip
\+\op void   del\_edge {edge\ e}      
                             {deletes the edge $e$ from $G$}
\smallskip
\+\op void       del\_all\_nodes {}
                             {deletes all nodes from $G$ }
\smallskip
\+\op void       del\_all\_edges {}
                             {deletes all edges from $G$ }
\smallskip
\+\op edge   rev\_edge {edge\ e}      
                             {reverses the edge $e = (v,w)$ by removing it }
\+\nop                       {from $G$ and inserting the edge $e\' = (w,v)$ }
\+\nop                       {into $G$ by appending it to the adjacency list}
\+\nop                       {of $w$, returns $e\'$ }
\smallskip
\+\op void   rev {}                 
                             {all edges in $G$ are reversed}
\smallskip
\+\op void   sort\_nodes {int (*cmp)(node\&,\ node\&)}  {}
\+\nop                       {the nodes of $G$ are sorted according to the}
\+\nop                       {ordering defined by the comparing function}
\+\nop                       {$cmp$. Subsequent executions of forall\_nodes}
\+\nop                       {step through the nodes in this order.}
\+\nop                       { (cf.~TOPSORT1 in section 8.1)}
\smallskip
\+\op void   sort\_nodes {node\_array\<T\>\ A}  {}
\+\nop                       {the nodes of $G$ are sorted according to the}
\+\nop                       {entries of node\_array $A$ (cf.~section 5.7)}
\+\nop                       {\precond $T$ must be linearly ordered}
\smallskip
\+\op void   sort\_edges {int (*cmp)(edge\&,\ edge\&)}  {}
\+\nop                       {the edges of $G$ are sorted according to the}
\+\nop                       {ordering defined by the comparing function}
\+\nop                       {$cmp$. Subsequent executions of forall\_edges}
\+\nop                       {step through the edges in this order.}
\+\nop                       { (cf.~TOPSORT1 in section 8.1)}
\smallskip
\+\op void   sort\_edges {edge\_array\<T\>\ A}  {}
\+\nop                       {the edges of $G$ are sorted according to the}
\+\nop                       {entries of edge\_array $A$ (cf.~section 5.7)}
\+\nop                       {\precond $T$ must be linearly ordered}
\smallskip
\+\op list\<edge\> insert\_reverse\_edges {} {}
\+\nop                       {for every edge $(v,w)$ in $G$ the reverse edge}
\+\nop                       {$(w,v)$ is inserted into $G$. The list of all}
\+\nop                       {inserted edges is returned.}
\smallskip
\+\op void   make\_undirected {}
                             {every edge $(v,w)$ in $G$ is inserted into the}
\+\nop                       {adjacency list of $w$.}
\smallskip
\+\op void   make\_directed {}
                             {every edge $(v,w)$ in $G$ is removed from the}
\+\nop                       {adjacency list of $w$.}
\smallskip
\+\op void   clear {}              
                             {makes $G$ the empty graph}

\vfill\eject

\bigskip
{\bf c) Iterators}
\medskip
With the adjacency list of every node $v$ is associated a list iterator 
called the adjacency iterator of $v$ (cf.~list). There are operations to 
initialize, move, and read these iterators. They are used to implement 
iteration statements (forall\_adj\_edges, forall\_adj\_nodes). 
\bigskip
\+\op void   init\_adj\_iterator {node\ v}         
                      {assigns nil to the adjacency iterator of node $v$}
\smallskip
\+\op bool   current\_adj\_edge {edge\&\ e,\ node\ v}  {}
\+\nop                {if the adjacency iterator of $v$ is defined ($\ne$ nil)} 
\+\nop                {its contents is assigned to $e$ and true is returned}
\+\nop                {else false is returned.}
\smallskip
\+\op bool   next\_adj\_edge {edge\&\ e,\ node\ v}     {}
\+\nop                {moves the adjacency iterator of $v$ forward (to the}
\+\nop                {first item of $adj\_list(v)$ if it is nil) and returns}
\+\nop                {$G$.current\_adj\_edge($e,v$)}
\smallskip
\+\op bool   current\_adj\_node {node\&\ w,\ node\ v}  {}
\+\nop                {if $G$.current\_adj\_edge($e$, $v$) = true then assign}
\+\nop                {$target(e)$ to w and return true, else return}
\+\nop                {false}
\smallskip
\+\op bool   next\_adj\_node {node\&\ w,\ node\ v}     {}
\+\nop                {if $G$.next\_adj\_edge($e$, $v$) = true then assign}
\+\nop                {$target(e)$ to w and return true, else return}
\+\nop                {false}
\smallskip
\+\op void   reset {}                          
                      {assign nil to all adjacency iterators in $G$}

\bigskip
{\bf d) Miscellaneous operations}
\medskip
\+\op void   write {ostream\ O\ =\ cout}        
                             {writes a compressed representation of $G$ to }
\+\nop                       {the output stream $O$.}
\smallskip
\smallskip
\+\op void   write {string\ s}        
                             {writes a compressed representation of $G$ to }
\+\nop                       {the file with name $s$.}
\smallskip
\+\op void   read {istream\ I\ =\ cin}         
                             {reads a compressed representation of $G$ from }
\+\nop                       {the input stream $I$.}
\smallskip
\+\op void   read {string\ s}         
                             {reads a compressed representation of $G$ from }
\+\nop                       {the file with name $s$.}
\smallskip
\+\op void   print\_node {node\ v,\ ostream\ O = cout} {}              
\+\nop                       {writes a readable representation of node $v$ to }
\+\nop                       {the output stream $O$}
\smallskip
\+\op void   print\_edge {edge\ e,\ ostream\ O = cout} {}              
\+\nop                       {writes a readable representation of edge $e$ to}
\+\nop                       {the output stream $O$}
\smallskip
\+\op void   print {ostream\ O = cout}              
                             {writes a readable representation of $G$ to the}
\+\nop                       {output stream $O$}

 
\bigskip
{\bf 4. Iteration}

{\bf forall\_nodes}($v,G$) 
$\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$

{\bf forall\_edges}($e,G$)  
$\{$ ``the edges of $G$ are successively assigned to $e$" $\}$

{\bf forall\_adj\_edges}($e,w$) \nl
\phantom{{\bf forall\_edges}($v,G$)}
$\{$ ``the edges adjacent to node w are successively assigned to e" $\}$

{\bf forall\_adj\_nodes}($v,w$) \nl  
\phantom{{\bf forall\_edges}($v,G$)}
$\{$ ``the nodes adjacent to node w are successively assigned to v" $\}$

\bigskip
{\bf 5. Implementation}

Graphs are implemented by doubly linked adjacency lists. Most operations 
take constant time, except of all\_nodes, all\_edges, del\_all\_nodes,
del\_all\_edges, clear, write, and read which take time $O(n+m)$, where 
$n$ is the current number of nodes and $m$ is the current number of edges. 
The space requirement is $O(n+m)$.

